package cn.itcast.zt.leetcode.string;
import java.util.*;

public class String_Algorithm {
    /**
     * 反转字符串 344
     * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
     */
    public void reverseString(char[] s) {
        if (s == null || s.length == 0) {
            return;
        }

        for (int i = s.length - 1, j = 0; i > j; i--, j++) {
            char temp = s[j] ;
            s[j] = s[i] ;
            s[i] = temp ;
        }
    }

    /**
     * 151. 反转字符串中的单词
     * @param s
     * @return
     */
    public String reverseWords(String s) {
        s = s.trim();
        List<String> wordList = Arrays.asList(s.split("\\s+")) ;
        Collections.reverse(wordList);
        return String.join(" ", wordList) ;
    }

    /**
     * 回文数  9
     * 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
     * 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
     */
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false ;
        }

        int num = x ;
        int res = 0 ;

        while(num != 0) {
            res = res * 10 + num % 10 ;
            num = num / 10 ;
        }

        return res == x ;
    }

    /**
     * 14. 最长公共前缀
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        String minStr = strs[0] ;
        for (int i = 1; i < strs.length; i++) {
            if (minStr.length() > strs[i].length()) {
                minStr = strs[i] ;
            }
        }

        Stack<String> popStr = new Stack<>() ;
        for (int k = 0; k < minStr.length(); k++) {
            popStr.push(minStr.substring(0, k+1)) ;
        }

        int size = popStr.size() ;
        if (!popStr.empty()) {
            L: for (int i = 0; i < size; i++) {
                String str = popStr.pop() ;
                for (int j = 0 ; j < strs.length ; j++) {
                    if (!strs[j].startsWith(str)) {
                        continue L;
                    }
                }

                return str ;
            }
        }

        return "" ;
    }

    /**
     * 28. 找出字符串中第一个匹配项的下标
     */
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle) ;
    }

    /**
     * 392. 判断子序列
     * @param s
     * @param t
     * @return
     */
    public boolean isSubsequence(String s, String t) {
        if (s.equals("")) {
            return true ;
        }

        String tt = new StringBuilder(t).reverse().toString() ;
        String[] arr = tt.split("") ;
        Stack<String> stack = new Stack<>() ;
        for (String st : arr) {
            stack.push(st) ;
        }

        String[] sArr = s.split("") ;

        int count = 0 ;
        L: for (int i = 0; i < sArr.length; i++) {
            String data = sArr[i];
            while(!stack.empty()) {
                String tmp = stack.pop() ;
                if (data.equals(tmp)) {
                    count ++ ;
                    continue L ;
                }
            }
        }

        if (count == sArr.length) {
            return true ;
        }

        return false ;
    }

    /**
     * 125. 验证回文串
     */
    public boolean isPalindrome(String s) {
        StringBuilder sgood = new StringBuilder() ;
        int length = s.length() ;
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i) ;
            if (Character.isLetterOrDigit(ch)) {
                sgood.append(Character.toLowerCase(ch)) ;
            }
        }

        StringBuilder sgood_rev = new StringBuilder(sgood).reverse() ;

        return sgood.toString().equals(sgood_rev);
    }

    /**
     * 同构字符串
     */
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> s2t = new HashMap<>();
        Map<Character, Character> t2s = new HashMap<>();

        int len = s.length() ;
        for (int i = 0; i < len; i++) {
            char x = s.charAt(i), y = t.charAt(i) ;
            if((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
                return false ;
            }

            s2t.put(x, y) ;
            t2s.put(y, x) ;
        }

        return true ;
    }

    /**
     * 存在重复元素 II
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>() ;
        int length = nums.length ;

        for (int i = 0; i < length; i++) {
            int num = nums[i] ;
            if (map.containsKey(num) && i - map.get(num) <= k) {
                return true ;
            }

            map.put(num, i) ;
        }

        return false ;
    }
}
